from time import time
from random import Random
from utils.clock import Clock
from utils.misc import INF

from stacking.solution import Solution


class HeuristicSolver(object):
    verbose = True
    filters = list()
    
    def __init__(self, heuristic=None):
        self.heuristic   = heuristic
        self.rng         = Random()
        self.clock       = Clock()
        self.instance    = None
        self.cursor      = None
        self.warehouse   = None
        self.crane       = None
        self.entrance    = None
        self.exit        = None
        self.solution    = None
        self.relocations = None
        self.time        = None
        
    # -------------------------------------------------------------------------
    # Main public method - solve(instance, seed=None)
    def solve(self, instance=None, seed=None, cut=+INF):
        self.initialize(instance, seed)
        self.run(cut)
        return self.finalize()
        
    def initialize(self, instance=None, seed=None):
        if instance is not None:
            self.instance = instance
        if self.instance is None:
            raise Exception("no instance provided")
        if seed is None:
            seed = int(time() * 1000)
        self.clock.clear()
        with self.clock.tracking():
            self.rng.seed(seed)
            self.warehouse   = self.instance.warehouse.deepcopy()
            self.crane       = iter(self.warehouse.cranes).next()
            self.entrance    = iter(self.warehouse.entrances).next()
            self.exit        = iter(self.warehouse.exits).next()
            self.cursor      = self.instance.calendar.cursor()
            self.solution    = Solution(self.instance, seed=seed, heur=self.heuristic.__name__)
            self.relocations = 0
            self.time        = -INF
            
    def run(self, cut=+INF):
        with self.clock.tracking():
            for _ in self.cursor:
                self.set_time(self.cursor.timestamp)
                self.process_deliveries()
                if self.verbose:
                    print "Total %d relocations." % self.relocations
                if self.relocations >= cut:
                    if self.verbose:
                        print "*** Upper bound reached. Solver aborted. ***"
                    self.solution = None
                    break
                self.process_releases()
                
    def finalize(self):
        if self.verbose:
            print("Finished running %s in %.3f seconds." % 
                  (self.heuristic.__name__, self.clock.total))
        if self.solution is not None:
            self.solution.meta.cpu = self.clock.total
            self.solution.meta.objective = self.relocations
            # +++ debugging code below
            items = set(self.instance.items.itervalues())
            items_with_release = set(i for i in items if i.release is not None)
            items_with_due     = set(i for i in items if i.due is not None)
            assert self.cursor.released  == items
            assert self.cursor.delivered == items_with_due
        return self.solution
        
    def set_time(self, t):
        assert t >= self.time
        self.time = t
        if self.verbose:
            print "\n", "-" * 100
            print "[[ t = %s ]]" % t
            
    def process_deliveries(self):
        cursor = self.cursor
        if len(cursor.deliveries) == 0:
            if self.verbose:
                print "No deliveries available at this time."
            return
            
        warehouse = self.warehouse
        deliveries = sorted(cursor.deliveries, key=lambda i: i.id)
        if self.verbose:
            print "Available for delivery: %s" % deliveries
        for item in deliveries:
            stack = warehouse.get_location(item)
            if stack is None:  # item was delivered and is not in the warehouse anymore
                continue
            # deliver the item *only if* its delivery interval ends this instant (it MUST be 
            # delivered now) or it can be delivered without relocations. Otherwise we postpone  
            # the delivery until we can do it without relocations or we reach the end of the 
            # interval (whichever comes first).
            if item in cursor.delivery_ends or stack.inversions == 0:
                self.deliver(item, stack)
                
    def process_releases(self):
        cursor = self.cursor
        if len(cursor.releases) == 0:
            if self.verbose:
                print "No releases available at this time."
            return
        
        warehouse = self.warehouse
        releases = sorted(cursor.releases, key=lambda i: i.id)
        if self.verbose:
            print "Available for release: %s" % releases
        for item in releases:
            # applying the same idea as above, we release an item *only if* either its release 
            # interval ends this instant (we MUST release it now), or we release it without 
            # causing inversions. If the item can't be released without creating new inversions 
            # AND it may be released later, then the release is postponed.
            if (item in cursor.release_ends or 
                not all(stack.creates_inversion(item) for stack in self.targets(item))):
                self.do_rpickup(item)
                self.store()
                # get rid of items that can be delivered immediately
                if item.due is not None and item.due.contains(self.time):
                    self.deliver(item, warehouse.get_location(item))
                    
    def targets(self, item, exclude=None):
        """Compute the set of currently eligible target stacks for placing 'item'. This removes 
        the stack passed through 'exclude' and applies any filters that may be in use."""
        warehouse = self.warehouse
        if exclude is None and len(self.filters) == 0:
            return warehouse.stacks
        eligible = set(warehouse.stacks)
        if exclude is not None:
            eligible.remove(exclude)
        for filter in self.filters:
            eligible = filter(item, eligible, warehouse)
        return eligible
        
    def store(self, exclude=None):
        """For each item currently in the crane, select a target stack and put the item down. When 
        relocating, the source stack can be avoided as a possible target using the 'exclude' 
        argument."""
        crane = self.crane
        while len(crane.items) > 0:
            item = crane.bottom
            targets = sorted(self.targets(item, exclude), key=lambda s: s.id)
            target = self.heuristic(item, targets, self.rng)
            self.do_putdown(target)
            
    def deliver(self, item, stack):
        """Deliver 'item' from 'stack' to the exit. For each item above the argument item, it is 
        delivered if the current simulation time is within its delivery interval, otherwise it is 
        relocated to some other eligible stack in the warehouse."""
        while True:
            self.do_pickup(stack)
            bottom = self.crane.bottom
            if bottom is item:
                self.do_dputdown()
                return  # argument item was delivered, stop the search
            if bottom.due is not None and bottom.due.contains(self.time):
                # crane bottom item is not what we're searching for, but we can 
                # deliver it now without relocations, so we do it for free :)
                self.do_dputdown()
            else:
                # relocate bottom item
                self.store(exclude=stack)
                
    # -------------------------------------------------------------------------
    # Convenience methods for creating, executing, and recording crane actions
    def do(self, action):
        """Execute an action in the warehouse and record the number of relocations made."""
        if self.verbose:
            print "Executing %s" % action
        self.relocations += self.warehouse.execute(action)
        if self.verbose and action.is_putdown:
            print self.warehouse, "\n"
            
    def do_rpickup(self, item):
        self.do(self.solution.rpickup([item.id], self.entrance.id))
        self.cursor.released_item(item)
        
    def do_pickup(self, source, n=1):
        assert len(source.items) >= n
        item_ids = [item.id for item in source.items[-n:]]
        if n > 1:
            item_ids.reverse()
        self.do(self.solution.pickup(item_ids, source.id))
        
    def do_dputdown(self):
        item = self.crane.bottom
        self.do(self.solution.dputdown([item.id], self.exit.id))
        self.cursor.delivered_item(item)
        
    def do_putdown(self, target, n=1):
        assert len(self.crane.items) >= n
        item_ids = [item.id for item in self.crane.items[-n:]]
        if n > 1:
            item_ids.reverse()
        self.do(self.solution.putdown(item_ids, target.id))
        
        
# -------------------------------------------------------------------------
# filters implementing optional constraints on stack selection
# to turn these on, simply add the functions to the solver's 'filters' list
def ceiling_filter(item, stacks, warehouse):
    """Filters out stacks where the given item cannot be placed because it will make the stack 
    taller than the specified maximum height."""
    ceiling = warehouse.meta.get("ceiling", None)
    if ceiling is None:
        return stacks
    return set(s for s in stacks if s.height + item.thickness <= ceiling)
    
    
def itemstack_filter(item, stacks, warehouse):
    """Filters stacks that cannot be selected as a valid target for 'item' because of item-stack 
    incompatibilities (e.g. item is too big to fit in the space where such stacks are located)."""
    compatible = item.meta.get("compatible_stacks", None)
    if compatible is None:
        return stacks
    return set(s for s in stacks if s.id in compatible)
    
    
##HeuristicSolver.filters.append(ceiling_filter)
##HeuristicSolver.filters.append(itemstack_filter)
